package com.success.fenbi;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 小混蛋
 * @CreateDate: 2018/12/20 17:22
 * @Desc：广度优先搜索，利用队列，本质上与二叉树层序遍历相同
 */
public class TheMazeBfs {
    public boolean bfs(boolean[][] maze) {
        Queue<int[]> queue = new LinkedList<int[]>();
        int[] root = {0, 0};
        int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int[][] used = new int[5][4];
        queue.add(root);
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == maze.length - 1 && cur[1] == maze[0].length - 1) {
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int posx = cur[0] + next[i][0];
                int posy = cur[1] + next[i][1];
                if (posx < 0 || posy < 0 || posx > maze.length - 1 || posy > maze[0].length - 1 || used[posx][posy] == 1 || !maze[posx][posy]) {
                    continue;
                }
                used[posx][posy] = 1;
                queue.add(new int[]{posx, posy});
            }
        }
        return false;
    }

    @Test
    public void test() {
        boolean[][] maze = new boolean[5][4];
        maze[0][0] = true;
        maze[0][1] = true;
        maze[1][1] = true;
        maze[1][2] = true;
        maze[2][2] = true;
        maze[3][2] = true;
        maze[4][2] = true;
        maze[4][3] = true;
        for (boolean[] row : maze) {
            for (boolean node : row) {
                System.out.print(node + "\t");
            }
            System.out.println("\b");
        }
        System.out.println(bfs(maze));
    }
}